package recursion;

import java.util.Scanner;

public class Test05 {

	public static void main(String[] args) {
		/*
		 * 用非递归方式写出斐波那契数列；
		 * 规则：
		 *	除了第一二位数以外，其他数都是其前两个数之和
		 * */
		System.out.println("输入一个数");
		Scanner sc=new Scanner(System.in);
		int num=sc.nextInt();
		System.out.println("第"+num+"个月，兔子数量为"+one(num));
		System.out.println("第"+num+"个月，兔子数量为"+two(num));
		System.out.println("第"+num+"个月，兔子数量为"+three(num));
		sc.close();
		
	}
	private static long one(int num) {
		/*
		 * 用参数转换的方式解决
		 * 
		 * 因为从第三位开始，一个数等于其前两个数之和
		 * 所以先设定one=1；two=1；
		 * for循环中改变其值
		 * add=one+two；
		 * one=two;
		 * two=add;
		 * 如果循环的值等于想要得到的值就退出循环，并返回add
		 * 
		 * */
		long add=0;
		long one=1;
		long two=1;
		if(num==1||num==2) {return 1;}else
		{for(int x=2;x<num;x++) {
			add=one+two;
			one=two;
			two=add;	
		}
		}return add;
	}
	private static long two(int num) {
		
		/*
		 * 用数组来求解
		 * 
		 * 设定数组的0和1其值为1；
		 * 第三位等于前两位相加，从而得出第三位，以此类推；
		 * */
		long[] arr=new long[num];
		if(num==1||num==2) {
			return 1;
		}else{
			  	arr[0]=1;
				arr[1]=1;
			
			  for(int x=2;x<num;x++) {
				  arr[x]=arr[x-1]+arr[x-2];
				  if(x==num) {
					  return arr[x];
				  }
			  } return arr[num-1];
		}
		
	}
	private static long three(int num) {
		if(num==1||num==2) {
			return 1;
		}return three(num-1)+three(num-2);
	}

}
